package xin.javashare.sort;

/**
 * 基本思想：
 * 在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；
 * 然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，
 * 依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
 */
public class SelectionSort {
    private static void swap(int[] a, int i, int j) {
        if (i == j) {
            return;
        }
        a[i] = a[i] + a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
    }

    public static void main(String[] args) {
        int a[] = {3, 1, 5, 7, 2, 4, 9, 6, 10, 8};
        SelectionSort obj = new SelectionSort();
        System.out.println("初始值：");
        obj.print(a);
        obj.selectionSort(a);
        System.out.println("\n排序后：");
        obj.print(a);

        System.out.println();
        int b[] = {3, 1, 5, 7, 2, 4, 9, 6, 10, 8};
        SelectionSort obj2 = new SelectionSort();
        System.out.println("初始值：");
        obj2.print(a);
        obj2.selectionSortBetter(a);
        System.out.println("\n排序后：");
        obj2.print(a);
    }

    public void selectionSort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int k = i;//k存放最小值下标
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[k]) {
                    k = j;
                }
                swap(a, k, i);//把最小的值放在它该放的位置
            }
        }
    }

    public void selectionSortBetter(int a[]) {
        int n = a.length;
        int i, j, min, max, temp;
        for (i = 0; i < n / 2; i++) {
            //不超过n/2趟
            min = i;
            max = n - 1 - i;
            for (j = i + 1; j < n - i; j++) {
                if (a[j] > a[max]) {
                    max = j;
                    continue;
                }
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            swap(a, i, min);
            swap(a, n - 1 - i, max);
        }
    }

    private void print(int[] a) {
        for (int anA : a) {
            System.out.print(anA + " ");
        }
    }
}
